package 剑指Offer.medium;

import java.util.ArrayList;
import java.util.List;

public class 机器人的运动范围 {
    class Solution {

        /**
         * @param m 格子行数
         * @param n 格子列数
         * @param k 数位和阈值
         * @return
         */
        public int movingCount(int m, int n, int k) {
            boolean[][] visited = new boolean[m][n];
            return dfs(m, n, 0, 0, k, visited);
        }

        /**
         *
         * @param m 格子行数
         * @param n 格子列数
         * @param x 坐标
         * @param y 坐标
         * @param k 数位和阈值
         * @param visited 标记是否访问
         * @return
         */
        public int dfs(int m, int n, int x, int y, int k, boolean[][] visited) {
            //判断是否越界,是否访问过,数位和是否符合规范
            if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || calculate(x) + calculate(y) > k) {
                return 0;
            }
            visited[x][y] = true;
            //只向右向下深搜
            return 1 + dfs(m, n, x + 1, y, k, visited) + dfs(m, n, x, y + 1, k, visited);
        }

        public int calculate(int x) {
            int sum = 0;
            while (x > 0) {
                sum += x % 10;
                x = x / 10;
            }
            return sum;
        }
    }
}
